package array

func spiralOrder(matrix [][]int) []int {
	dirs := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
	res := make([]int, 0)
	n, m := len(matrix), len(matrix[0])
	i, j := 0, 0
	vis := make([][]bool, n)
	for i := 0; i < n; i++ {
		vis[i] = make([]bool, m)
	}
	idx := 0
	for len(res) != n*m {
		res = append(res, matrix[i][j])
		vis[i][j] = true
		nextI := i + dirs[idx][0]
		nextJ := j + dirs[idx][1]
		if nextI < 0 || nextI >= n || nextJ < 0 || nextJ >= m || vis[nextI][nextJ] {
			idx = (idx + 1) % 4
		}
		i += dirs[idx][0]
		j += dirs[idx][1]
	}
	return res
}
